def activity_selection(start, end):
    """
    贪心算法解决活动选择问题：选择最多的互不冲突的活动
    参数：
        start: 列表，每个元素为活动的开始时间
        end: 列表，每个元素为对应活动的结束时间
    返回：
        选中的活动列表（每个元素为(start, end)元组）
    """
    # 1. 计算活动数量
    n = len(end)
    if n == 0:
        return []  # 没有活动时返回空列表

    # 2. 按结束时间从小到大排序活动（核心步骤）
    # 用zip将start和end打包成元组，再按元组的第二个元素（结束时间）排序
    activities = sorted(zip(start, end), key=lambda x: x[1])

    # 3. 贪心选择：从第一个活动开始，依次选不冲突的活动
    selected_activities = []
    # 选第一个活动（结束时间最早的）
    selected_activities.append(activities[0])
    last_end = activities[0][1]  # 记录上一个选中活动的结束时间

    # 遍历剩余活动
    for i in range(1, n):
        current_start, current_end = activities[i]
        # 若当前活动的开始时间 >= 上一个活动的结束时间，说明不冲突，可选择
        if current_start >= last_end:
            selected_activities.append(activities[i])
            last_end = current_end  # 更新最后结束时间

    return selected_activities



if __name__ == "__main__":

    start_times = [1, 3, 0, 5, 8, 5]
    end_times = [2, 4, 6, 7, 9, 9]


    selected = activity_selection(start_times, end_times)


    print(f"最多可选择 {len(selected)} 个互不冲突的活动，分别是：")
    for act in selected:
        print(f"开始时间：{act[0]}，结束时间：{act[1]}")